package com.explorati.dongtaiguihua.fibonaccisequence;

/**
 * 斐波那锲数列 动态规划基础
 * 
 * 解决存在的问题 方法二：自下而上的解决问题
 * 
 * @author explorati
 *
 */
public class Solution1 {
	public static int fibonacci(int n) {
		int[] memo = new int[n + 1];

		memo[0] = 0;
		memo[1] = 1;
		for (int i = 2; i <= n; i++) {
			memo[i] = memo[i - 1] + memo[i - 2];
		}

		return memo[n];
	}

	public static void main(String[] args) {
		int n = 40;

		long startTime = System.nanoTime();
		int res = fibonacci(n);
		long endTime = System.nanoTime();
		System.out.println("fibonacci(" + n + ") =" + res);
		System.out.println("time : " + (endTime - startTime) / 1000000000.0 + "s");
	}
}
